#include <iostream>
#include <cassert>
#include <math.h>

using namespace std;

template<typename Item>
class MaxHeap {

private:
    Item *data;
    int count;
    int capacity;



    void shiftUp(int k) {

        //优化点，将交换变成赋值后插入
        Item v = data[k];

        //while (k > 1 && data[k / 2] < data[k]) {
        while (k > 1 && data[k / 2] < v) {
            //swap(data[k / 2], data[k]);

            data[k] = data[k / 2];
            k /= 2;
        }

        data[k] = v;
    }

    void shiftDown(int k) {

        //优化点：将多次交换变为赋值后插入
        Item v = data[k];

        while (2 * k <= count) {//判断数组有没有越界

            int j = 2 * k;      //在本次循环中，索引k与j的进行交换（默认左孩子）

            if (j < count && data[j + 1] > data[j]) {  //寻找较大的孩子结点，
                j += 1;
            }

//            if (data[k] >= data[j]) {   //父节点与较大的孩子大于相等就不交换
//                break;
//            }

            if (v >= data[j]) {   //待调整元素与将挑换元素大于相等就不赋值
                break;
            }

            //swap(data[k], data[j]);   //替换父子节点位置
            data[k] = data[j];      //将替换元素数值赋值给父节点

            k = j;      //下一个待调整元素的索引位置
        }
        data[k] = v;
    }

public:
    MaxHeap(int capacity) {
        data = new Item[capacity + 1];
        count = 0;
        this->capacity = capacity;
    }

    ~MaxHeap() {
        delete[] data;
    }

    int size() {
        return count;
    }

    bool isEmpty() {
        return count == 0;
    }

    void insert(Item item) {

        assert(count + 1 <= capacity);

        data[count + 1] = item;
        count++;
        shiftUp(count);
    }

    Item extracMax() {

        assert(count > 0);      //堆是否为空

        Item ret = data[1];     //返回最大的值

        swap(data[1], data[count]); //交换最大的结点与最后一个结点；也可以将最后一个元素赋值给第一个元素

        count--;        //堆大小减1

        shiftDown(1);   //维护堆，将data[i]的元素调整到应该的位置

        return ret;
    }

public:
    void testPrint() {

        if (size() >= 100) {
            cout << "Fancy print can only work for less than 100 int";
            return;
        }

        if (typeid(Item) != typeid(int)) {
            cout << "Fancy print can only work for int item";
            return;
        }

        cout << "The Heap size is: " << size() << endl;
        cout << "data in heap: ";
        for (int i = 1; i <= size(); i++)
            cout << data[i] << " ";
        cout << endl;
        cout << endl;

        int n = size();
        int max_level = 0;
        int number_per_level = 1;
        while (n > 0) {
            max_level += 1;
            n -= number_per_level;
            number_per_level *= 2;
        }

        int max_level_number = int(pow(2, max_level - 1));
        int cur_tree_max_level_number = max_level_number;
        int index = 1;
        for (int level = 0; level < max_level; level++) {
            string line1 = string(max_level_number * 3 - 1, ' ');

            int cur_level_number = min(count - int(pow(2, level)) + 1, int(pow(2, level)));
            bool isLeft = true;
            for (int index_cur_level = 0; index_cur_level < cur_level_number; index++, index_cur_level++) {
                putNumberInLine(data[index], line1, index_cur_level, cur_tree_max_level_number * 3 - 1, isLeft);
                isLeft = !isLeft;
            }
            cout << line1 << endl;

            if (level == max_level - 1)
                break;

            string line2 = string(max_level_number * 3 - 1, ' ');
            for (int index_cur_level = 0; index_cur_level < cur_level_number; index_cur_level++)
                putBranchInLine(line2, index_cur_level, cur_tree_max_level_number * 3 - 1);
            cout << line2 << endl;

            cur_tree_max_level_number /= 2;
        }
    }

private:
    void putNumberInLine(int num, string &line, int index_cur_level, int cur_tree_width, bool isLeft) {

        int sub_tree_width = (cur_tree_width - 1) / 2;
        int offset = index_cur_level * (cur_tree_width + 1) + sub_tree_width;
        assert(offset + 1 < line.size());
        if (num >= 10) {
            line[offset + 0] = '0' + num / 10;
            line[offset + 1] = '0' + num % 10;
        } else {
            if (isLeft)
                line[offset + 0] = '0' + num;
            else
                line[offset + 1] = '0' + num;
        }
    }

    void putBranchInLine(string &line, int index_cur_level, int cur_tree_width) {

        int sub_tree_width = (cur_tree_width - 1) / 2;
        int sub_sub_tree_width = (sub_tree_width - 1) / 2;
        int offset_left = index_cur_level * (cur_tree_width + 1) + sub_sub_tree_width;
        assert(offset_left + 1 < line.size());
        int offset_right = index_cur_level * (cur_tree_width + 1) + sub_tree_width + 1 + sub_sub_tree_width;
        assert(offset_right < line.size());

        line[offset_left + 1] = '/';
        line[offset_right + 0] = '\\';
    }

};

int main() {
    MaxHeap<int> maxHeap = MaxHeap<int>(100);
    cout << maxHeap.size() << endl;

    srand(time(NULL));
    for (int i = 0; i < 50; ++i) {
        maxHeap.insert(rand() % 100);
    }

    maxHeap.testPrint();
    cout << endl;

    while (!maxHeap.isEmpty()) {
        cout << maxHeap.extracMax() << " ";
    }
    cout << endl;

    return 0;
}